package Test;

/**
 * @leiwenkang 2017-12-29 16:11.
 */
public class HeapSort {
    public static void main(String[] args) {
        int[] array = {3, 6, 4, 7, 9, 1, 5, 8, 2};
        heapSort(array);
        for (int i = 0; i < array.length; i++) {
            System.out.println(array[i]);
        }
    }

    public static void heapSort(int[] array){
        if (array == null || array.length == 0){
            return;
        }
        for (int i = array.length/2 - 1; i >= 0; i--){
            adjustHeap(array,i,array.length-1);
        }
        for (int i = array.length - 1; i >= 0; i--) {
            int temp = array[0];
            array[0] = array[i];
            array[i] = temp;
            adjustHeap(array, 0 , i - 1);
        }
    }

    private static void adjustHeap(int[] array, int index, int end) {
          for(int i = 2 * index + 1; i <= end; i = 2 * i + 1) {
              if (i < end && array[i] < array[i + 1]) {
                  i++;
              }
              if (array[i] <= array[index]) {
                  break;
              }
              int temp = array[i];
              array[i] = array[index];
              array[index] = temp;
              index = i;
          }
    }
}
